﻿//2806. 取整购买后的账户余额
class Solution {
public:
    int accountBalanceAfterPurchase(int purchaseAmount) {
        int r = purchaseAmount % 10;
        if (r < 5) {
            purchaseAmount -= r;
        }
        else {
            purchaseAmount += 10 - r;
        }
        return 100 - purchaseAmount;
    }
};

//2786. 访问数组中的位置使分数最大
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        long long ret = nums[0];
        vector<long long> dp(2, INT_MIN);
        dp[nums[0] % 2] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int parity = nums[i] % 2;
            long long cur = max(dp[parity] + nums[i], dp[1 - parity] - x + nums[i]);
            ret = max(ret, cur);
            dp[parity] = max(dp[parity], cur);
        }
        return ret;
    }
};

//2779. 数组的最大美丽值
class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int ret = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0, j = 0;i < nums.size();i++) {
            while (nums[i] - 2 * k > nums[j]) {
                j++;
            }
            ret = max(ret, i - j + 1);
        }
        return ret;
    }
};

//521.最长特殊序列
class Solution {
public:
    int findLUSlength(string a, string b) {
        return a != b ? max(a.length(), b.length()) : -1;
    }
};

//522.最长特殊序列||
class Solution {
    bool isSubseq(string& s, string& t) {
        int i = 0;
        for (char c : t) {
            if (s[i] == c && ++i == s.size())
                return true;
        }
        return false;
    }
public:
    int findLUSlength(vector<string>& strs) {
        int ret = -1;
        for (int i = 0;i < strs.size();i++) {
            if ((int)strs[i].size() <= ret)
                continue;
            for (int j = 0;j < strs.size();j++) {
                if (j != i && isSubseq(strs[i], strs[j]))
                    goto next;
            }
            ret = strs[i].size();
        next:;
        }
        return ret;
    }
};

//2288. 价格减免
class Solution {
public:
    string discountPrices(string sentence, int discount) {
        double d = 1 - discount / 100.0;
        stringstream ss(sentence);
        string ret, v;
        while (ss >> v) {
            if (!ret.empty())
                ret += ' ';
            if (v.length() > 1 && v[0] == '$' && all_of(v.begin() + 1, v.end(), ::isdigit)) {
                stringstream s;
                s << fixed << setprecision(2) << '$' << stoll(v.substr(1)) * d;
                ret += s.str();
            }
            else
                ret += v;
        }
        return ret;
    }
};

//2713. 矩阵中严格递增的单元格数
class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        map<int, vector<pair<int, int>>> mp;
        vector<int> row(m), col(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mp[mat[i][j]].push_back({ i, j });
            }
        }

        vector<int> res; // 存放相同数值的答案，便于后续更新 row 和 col
        for (auto& [_, pos] : mp) {
            res.clear();
            for (auto& [x, y] : pos) {
                res.push_back(max(row[x], col[y]) + 1);
            }
            for (int i = 0; i < pos.size(); i++) {
                auto& [x, y] = pos[i];
                row[x] = max(row[x], res[i]);
                col[y] = max(col[y], res[i]);
            }
        }
        return *max_element(row.begin(), row.end());
    }
};

//2748. 美丽下标对的数目
class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int ret = 0, n = nums.size();
        for (int i = 0;i < n;i++) {
            while (nums[i] >= 10)
                nums[i] /= 10;
            for (int j = i + 1;j < n;j++) {
                if (gcd(nums[i], nums[j] % 10) == 1)
                    ret++;
            }
        }
        return ret;
    }
};

//LCP 61. 气温变化趋势
class Solution {
public:
    int temperatureTrend(vector<int>& a, vector<int>& b) {
        auto cmp = [](int x, int y) {return (x > y) - (x < y);};
        int ret = 0, sam = 0;
        for (int i = 1; i < a.size();i++) {
            if (cmp(a[i - 1], a[i]) == cmp(b[i - 1], b[i]))
                ret = max(ret, ++sam);
            else
                sam = 0;
        }
        return ret;
    }
};

//2663. 字典序最小的美丽字符串
class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        k += 'a';
        int n = s.length();
        int i = n - 1; // 从最后一个字母开始
        s[i]++; // 先加一
        while (i < n) {
            if (s[i] == k) { // 需要进位
                if (i == 0) { // 无法进位
                    return "";
                }
                // 进位
                s[i] = 'a';
                s[--i]++;
            }
            else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
                s[i]++; // 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i]
            }
            else {
                i++; // 反过来检查后面是否有回文串
            }
        }
        return s;
    }
};

//520. 检测大写字母
class Solution {
public:
    bool detectCapitalUse(string word) {
        //int cnt = ranges::count_if(word, [](char c) { return isupper(c); });
        //return cnt == 0 || cnt == word.length() || cnt == 1 && isupper(word[0]);
        // 若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写
        if (word.size() >= 2 && islower(word[0]) && isupper(word[1])) {
            return false;
        }

        // 无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同
        for (int i = 2; i < word.size(); ++i) {
            if (islower(word[i]) ^ islower(word[1])) {
                return false;
            }
        }
        return true;

    }
};

//503. 下一个更大元素 II
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, -1);
        stack<int> s;
        for (int i = 2 * n - 1;i >= 0;i--) {
            int x = nums[i % n];
            while (!s.empty() && x >= s.top()) {
                s.pop();
            }
            if (i < n && !s.empty())
                ret[i] = s.top();
            s.push(x);
        }
        return ret;
    }
};

//2741. 特别的排列
class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size(), u = (1 << n) - 1;
        vector<vector<long long>> memo(u, vector<long long>(n, -1)); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int s, int i) -> long long {
            if (s == 0) {
                return 1; // 找到一个特别排列
            }
            auto& res = memo[s][i]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            for (int j = 0; j < n; j++) {
                if ((s >> j & 1) && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                    res += dfs(dfs, s ^ (1 << j), j);
                }
            }
            return res;
        };
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dfs(dfs, u ^ (1 << i), i);
        }
        return ans % 1'000'000'007;
    }
};

//2734. 执行子串操作后的字典序最小字符串
class Solution {
public:
    string smallestString(string s) {
        int n = s.size();
        for (int i = 0;i < n;i++) {
            if (s[i] > 'a') {
                for (;i < n && s[i]> 'a';i++)
                    s[i]--;
                return s;
            }
        }
        s.back() = 'z';
        return s;
    }
};

//
class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        for (int i = 0; i < matrix[0].size(); i++) {
            int mx = 0;
            for (auto& row : matrix)
                mx = max(mx, row[i]);
            for (auto& row : matrix) {
                if (row[i] == -1)
                    row[i] = mx;
            }
        }
        return matrix;
    }
};

//1958. 检查操作是否合法
class Solution {
    int dirs[8][2] = { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} };
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int m = board.size(), n = board[0].size();
        for (auto& dir : dirs) {
            int x = rMove + dir[0];
            int y = cMove + dir[1];
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != (color ^ 'B' ^ 'W'))
                continue;
            while (true) {
                x += dir[0];
                y += dir[1];
                if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] == '.')
                    break;
                if (board[x][y] == color)
                    return true;
            }
        }
        return false;
    }
};

//单词搜索（dfs 深度优先遍历）
#include <vector>
class Solution {
public:
    int r, l;
    bool dfs(vector<string>& board, string word, int i, int j, int k) {
        if (i >= r || i < 0 || j >= l || j < 0 || board[i][j] != word[k])return false;
        if (k == word.size() - 1)return true;
        board[i][j] = '\0';
        bool res = dfs(board, word, i + 1, j, k + 1) ||
            dfs(board, word, i - 1, j, k + 1) ||
            dfs(board, word, i, j + 1, k + 1) ||
            dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
    bool exist(vector<string>& board, string word) {
        r = board.size();
        l = board[0].size();
        for (int i = 0;i < r;i++)
            for (int j = 0;j < l;j++)
                if (dfs(board, word, i, j, 0))return true;
        return false;
    }
};

//游游的you
#include <iostream>
using namespace std;

int main() {
    int q = 0;
    int a = 0;
    int b = 0;
    int c = 0;
    cin >> q;
    while (q--) {
        cin >> a >> b >> c;
        int you = 0;
        while (a != 0 && b != 0 && c != 0) {
            a--, b--, c--;
            you += 2;
        }
        while (a != 0) {
            a--;
        }
        int oo = 0;
        int m = 0;
        int flag = 0;
        while (b != 0) {
            flag = 1;
            b--;
            m++;
        }
        if (flag) oo = m - 1;
        else oo = m;
        while (c != 0) {
            c--;
        }
        cout << (you + oo) << endl;
    }
    return 0;
}

//腐烂的苹果
class Solution {
    int m, n;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    bool vis[1001][1001] = { false };
    queue<pair<int, int>> badapple;

public:
    int rotApple(vector<vector<int> >& grid) {
        n = grid.size();
        m = grid[0].size();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2)
                    badapple.push({ i, j });
            }
        }

        int count = 0;
        while (badapple.size()) {
            count++;
            int sz = badapple.size();
            while (sz--) {
                auto [a, b] = badapple.front();
                badapple.pop();
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y]) {
                        vis[x][y] = true;
                        badapple.push({ x, y });
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !vis[i][j])
                    return -1;
            }
        }
        return count - 1;
    }
};
//孩子们的游戏
class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        list<int> lt;
        for (int i = 0; i < n; i++) {
            lt.push_back(i);
        }
        auto it = lt.begin();
        while (lt.size() > 1) {
            for (int count = 1; count < m; ++count) {
                ++it;
                if (it == lt.end()) {
                    it = lt.begin();
                }
            }
            it = lt.erase(it);
            if (it == lt.end())
                it = lt.begin();
        }
        return *it;
    }
};
//大数加法
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string ret; //存储两个字符串相加后的结果
        int carry = 0; //进位（初始时进位设置为0）
        while (end1 >= 0 || end2 >= 0) {
            int a = 0;
            if (end1 >= 0) {
                a = num1[end1] - '0';
                end1--;
            }
            int b = 0;
            if (end2 >= 0) {
                b = num2[end2] - '0';
                end2--;
            }
            int sum = a + b + carry;
            if (sum > 9) {
                sum -= 10;
                carry = 1;
            }
            else {
                carry = 0;
            }
            ret += (sum + '0');
        }
        if (carry != 0)
            ret += '1';

        reverse(ret.begin(), ret.end());
        return ret;
    }
};
//链表相加
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* pre1 = NULL;
        ListNode* p1 = head1;
        ListNode* pre2 = NULL;
        ListNode* p2 = head2;
        while (p1) { //逆转head1链表
            ListNode* tmp = p1->next;
            p1->next = pre1;
            pre1 = p1;
            p1 = tmp;
        }
        while (p2) { //逆置head2链表
            ListNode* tmp = p2->next;
            p2->next = pre2;
            pre2 = p2;
            p2 = tmp;
        }
        int flag = 0;  //进位标志
        int sum = 0;  //当前节点之和（余10）
        ListNode* dummy = new ListNode(-1); //新链表的头结点
        ListNode* p = dummy;
        while (pre1 || pre2) {
            int val1 = 0, val2 = 0;
            if (pre1) {
                val1 = pre1->val;
                pre1 = pre1->next;
            }
            if (pre2) {
                val2 = pre2->val;
                pre2 = pre2->next;
            }
            sum = (val1 + val2 + flag) % 10;
            flag = (val1 + val2 + flag) / 10;
            ListNode* tmpnode = new ListNode(sum);
            tmpnode->next = p->next;
            p->next = tmpnode;
        }
        if (flag) { //第一个结点相加后有进位
            ListNode* tmpnode = new ListNode(1);
            tmpnode->next = p->next;
            p->next = tmpnode;
        }
        return dummy->next;
    }
};
//
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string num1, string num2) {
        if (num1 == "0" || num2 == "0") //两个操作数中有一个为0，则结果为0
            return "0";

        int m = num1.size(), n = num2.size();
        vector<int> arr(m + n, 0);
        //1、取乘数的每一位与被乘数的每一位相乘，将结果累加到数组arr的对应下标位置
        for (int i = n - 1; i >= 0; i--) { //取乘数的每一位
            int a = num2[i] - '0';
            for (int j = m - 1; j >= 0; j--) { //取被乘数的每一位
                int b = num1[j] - '0';
                arr[i + j + 1] += a * b; //乘数第i位与被乘数第j位相乘后的结果累加到数组arr中下标为i+j+1的位置
            }
        }
        //2、从后往前对数组arr进行进位操作
        int end = m + n - 1;
        while (end > 0) {
            arr[end - 1] += arr[end] / 10; //进位的值加到前一个位置
            arr[end] %= 10; //进位后剩下的值存放到当前位
            end--; //处理下一位
        }
        //3、依次将数据尾插到字符串ret当中
        string ret;
        int flag = 1; //默认有效值从数组arr当中下标为1的位置开始
        if (arr[0] != 0)
            flag = 0; //若数组arr当中下标为0的位置的值不为0，则有效值从第0位开始
        for (int i = flag; i < m + n; i++) {
            ret += (arr[i] + '0');
        }
        return ret;
    }
};

//在字符串中找出最长连续数字子串
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        string ret;
        string tmp;
        for (int i = 0;i < str.size();) {
            while (i < str.size() && str[i] >= '0' && str[i] <= '9')
            {
                tmp += str[i];
                i++;
            }
            if (tmp.size() > ret.size())
                ret = tmp;
            tmp.clear();
            i++;
        }
        cout << ret << endl;
    }
    return 0;
}

//岛屿数量（测试用例80%）
#include <queue>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */
    int dx[4] = { 0, 1, 0, -1 };
    int dy[4] = { 1, 0, -1, 0 };
    bool vis[201][201];
    int m, n;

    int solve(vector<vector<char> >& grid) {
        n = grid.size(), m = grid[0].size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1' && vis[i][j] == false) {
                    bfs(i, j, grid);
                    ret++;
                }
            }
        }
        return ret;
    }
    void bfs(int sx, int sy, vector<vector<char>>& grid) {
        queue<pair<int, int>>pq;
        pq.push({ sx, sy });
        vis[sx][sy] = true;
        while (!pq.empty()) {
            auto [a, b] = pq.front();
            pq.pop();
            for (int k = 0; k < 4; k++) {
                int rx = a + dx[k];
                int ry = b + dy[k];
                if (rx < 0 || rx >= n || ry < 0 || ry >= m | grid[rx][ry] == '0' || vis[rx][ry])
                    continue;
                vis[rx][ry] = true;
                pq.push({ rx, ry });
            }
        }
    }
};

//拼三角
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    int a, b, c, d, e, f;
    cin >> t;
    vector<int>s(6);
    while (t--) {
        bool flag = false;
        for (int i = 0;i < 6;i++)
            cin >> s[i];
        sort(s.begin(), s.end());
        do {
            a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], f = s[5];
            if (a + b > c &&
                a + c > b &&
                b + c > a &&
                d + e > f &&
                d + f > e &&
                f + e > d) {
                flag = true;
                break;
            }
        } while (next_permutation(s.begin(), s.end()));
        //next_permutation全排列函数
        if (flag)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
//最长连续子序列
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& nums) {
        unordered_set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longestStreak = 0;

        for (const int& num : num_set) {
            if (!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};
//字母识别
#include <iostream>
using namespace std;

const int N = 501;
char ch[N][N];
int dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ch[i][j];
        }
    }

    int score = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ch[i][j] == 'l')
                score = 4;
            else if (ch[i][j] == 'o')
                score = 3;
            else if (ch[i][j] == 'v')
                score = 2;
            else if (ch[i][j] == 'e')
                score = 1;
            else
                score = 0;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + score;
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

//过河卒（90%）
#include<iostream>
using namespace std;
int a[50][50];
int main() {
    int n, m, x, y, i, j;
    cin >> n >> m >> x >> y;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)a[i][j] = 1;
    }
    a[x][y] = 0;
    if (x - 1 >= 0 && y - 2 >= 0)a[x - 1][y - 2] = 0; //将马的控制点设为0
    if (x - 2 >= 0 && y - 1 >= 0)a[x - 2][y - 1] = 0; //将马的控制点设为0
    if (x - 2 >= 0 && y + 1 <= m)a[x - 2][y + 1] = 0; //将马的控制点设为0
    if (x - 1 >= 0 && y + 2 <= m)a[x - 1][y + 2] = 0; //将马的控制点设为0
    if (x + 1 <= n && y + 2 <= m)a[x + 1][y + 2] = 0; //将马的控制点设为0
    if (x + 2 <= n && y + 1 <= m)a[x + 2][y + 1] = 0; //将马的控制点设为0
    if (x + 2 <= n && y - 1 >= 0)a[x + 2][y - 1] = 0; //将马的控制点设为0
    if (x + 1 <= n && y - 2 >= 0)a[x + 1][y - 2] = 0; //将马的控制点设为0
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && i == j)continue;
            if (a[i][j] == 0)continue; //跳过
            if (i == 0)
                a[i][j] = a[i][j - 1];
            if (j == 0)a[i][j] = a[i - 1][j];
            if (i != 0 && j != 0 && a[i][j] != 0)
                a[i][j] = a[i - 1][j] + a[i][j - 1];
        }
    }
    cout << a[n][m] << endl;
    return 0;
}

//两链表的第一个公共结点
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        int size1 = 0;
        int size2 = 0;
        ListNode* cur1 = pHead1;
        ListNode* cur2 = pHead2;
        while (cur1)
        {
            size1++;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            size2++;
            cur2 = cur2->next;
        }
        int dif = abs(size1 - size2);
        cur1 = pHead1;
        cur2 = pHead2;
        if (size1 > size2)
            while (dif--)
                cur1 = cur1->next;
        if (size2 > size1)
            while (dif--)
                cur2 = cur2->next;
        while (cur1 || cur2)
        {
            if (cur1 == cur2)
                return cur1;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return nullptr;
    }
};

//mari和shiny
#include <iostream>
#include <string>
using namespace std;
#define int long long
const int N = 3e5 + 10;
int s[N];
int h[N];
int y[N];
char str[N];

signed main() {
    int n;
    cin >> n;

    for (int i = 0; i < n;++i)
    {
        cin >> str[i];
    }

    s[0] = str[0] == 's' ? 1 : 0;
    h[0] = y[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == 's')
            s[i] = s[i - 1] + 1;
        else
            s[i] = s[i - 1];

        if (str[i] == 'h')
            h[i] = s[i - 1] + h[i - 1];
        else
            h[i] = h[i - 1];

        if (str[i] == 'y')
            y[i] = h[i - 1] + y[i - 1];
        else
            y[i] = y[i - 1];
    }

    cout << y[n - 1] << endl;
    return 0;
}

//牛牛冲钻石
#include <iostream>
using namespace std;

int n, k;
void solve() {
    cin >> n >> k;

    string s;
    cin >> s;

    int sum = 0;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'W') {
            if (cnt >= 2) {
                sum += k;
            }
            else {
                sum += 1;
            }
            cnt++;
        }
        else {
            sum -= 1;
            cnt = 0;
        }
    }
    cout << sum << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}
//最长无重复子数组
// 哈希＋双指针
class Solution {
public:
    int cnt[100010] = { 0 };
    int maxLength(vector<int>& arr) {
        int n = arr.size();

        int l = 0;
        int r = 0;
        int len = 0;
        while (r < n) {
            cnt[arr[r]]++;// 进窗口
            while (cnt[arr[r]] > 1) { // 出窗口（条件）
                cnt[arr[l]]--;
                l++;
            }
            len = max(len, r - l + 1);
            r++;
        }
        return len;
    }
};
//重排字符串
#include <iostream>
using namespace std;
const int N = 100010;
int n;
char s[N];
char ret[N];
int main() {
    cin >> n >> s;

    int cnt[26] = { 0 }; // 统计每个字符的频次
    int maxIndex, maxCount = 0;
    for (int i = 0; i < n; i++) {
        if (maxCount < ++cnt[s[i] - 'a']) {
            maxCount = cnt[s[i] - 'a'];
            maxIndex = s[i] - 'a';
        }
    }

    if (maxCount > (n + 1) / 2)
        cout << "no" << endl;
    else {
        cout << "yes" << endl;
        int index = 0;
        // 先去摆放出现次数最多的
        while (maxCount--) {
            ret[index] = maxIndex + 'a';
            index += 2;
        }
        // 处理剩下的
        for (int i = 0; i < 26; i++) {
            if (cnt[i] && i != maxIndex) {
                while (cnt[i]--) {
                    if (index >= n) index = 1;
                    ret[index] = i + 'a';
                    index += 2;
                }
            }
        }
        // 打印结果
        for (int i = 0; i < n; i++) cout << ret[i];
        cout << endl;
    }

    return 0;
}

//乒乓球框
#include <iostream>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int s1[26] = { 0 };
    int s2[26] = { 0 };
    for (int i = 0; i < str1.size(); i++) {
        s1[str1[i] - 'A']++;
    }
    for (int i = 0; i < str2.size(); i++) {
        s2[str2[i] - 'A']++;
    }
    for (int i = 0; i < 26; i++) {
        if (s1[i] < s2[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}
//组队竞赛
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL arr[N * 3];
int main() {
    cin >> n;
    for (int i = 0; i < 3 * n; i++) cin >> arr[i];
    sort(arr, arr + 3 * n);
    int pos = 3 * n - 2, count = 1;
    LL ret = 0;
    while (count++ <= n) {
        ret += arr[pos];
        pos -= 2;
    }
    cout << ret << endl;
    return 0;
}
//删除相邻数字的最⼤分数
#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int sum[N];
int f[N];
int g[N];

int main() {
    int n;
    cin >> n;

    int x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        sum[x] += x;
    }

    for (int i = 0; i < N; ++i) {
        f[i] = sum[i] + g[i - 1];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(f[N - 1], g[N - 1]) << endl;

    return 0;
}

//平方数
#include <cmath>
#include <iostream>
using namespace std;
#define int long long
signed main() {
    int x;
    cin >> x;
    int tmp = (int)(sqrt(x) + 0.5);
    cout << tmp * tmp << endl;
}
//分组 
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map<int, int> umap;
int n, m;

bool Check(int x) // 每组人数最多为x时
{
    int g = 0;
    for (auto& [a, b] : umap)
    {
        g += b / x + (b % x == 0 ? 0 : 1);
    }
    return g <= m;
}

int main()
{
    cin >> n >> m;

    int x;
    int maxn = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        maxn = max(maxn, ++umap[x]);
    }
    int kinds = umap.size();
    if (kinds > m)
        cout << -1 << endl;
    else
    {
        if (kinds == m)
            cout << maxn << endl;
        else
        {
                int l = 1;
            int r = maxn;
            while (l < r)
            {
                int mid = l + (r - l) / 2;
                if (Check(mid))
                    r = mid;
                else
                    l = mid + 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}
//拓扑排序
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;

int n, m, a, b;
int in[N];
int ret[N];
int k = 0;
int main() {
    cin >> n >> m;

    // 构图
    unordered_map<int, vector<int>> edges;
    for (int i = 0; i < 2 * (n - 1); ++i)
    {
        cin >> a >> b;
        edges[a].push_back(b);
        in[b]++;
    }

    // 存入度为一的数
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (in[i] == 0)
            q.push(i);

    while (q.size())
    {
        int top = q.front();
        q.pop();

        ret[k++] = top;
        for (int e : edges[top])
        {
            in[e]--;
            if (in[e] == 0)
                q.push(e);
        }
    }

    int flag = 1;
    for (int i = 1; i <= n; ++i)
        if (in[i] != 0)
        {
            cout << -1 << endl;
            flag = 0;
            break;
        }

    if (flag)
    {
        for (int i = 0; i < k - 1; ++i)
            cout << ret[i] << " ";
        cout << ret[k - 1];
    }

    return 0;
}

//字符串替换
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串 原串
     * @param arg char字符型vector 需替换数组
     * @return string字符串
     */
    string formatString(string str, vector<char>& arg) {
        string ret;
        int i, k = 0;
        for (i = 0; i < str.size(); i++) {
            if (str[i] == '%') {
                ret += arg[k++];
                i++;
            }
            else {
                ret += str[i];
            }
        }
        while (k < arg.size()) {
            ret += arg[k++];
        }
        return ret;
    }
};
//神奇数
#include <iostream>
using namespace std;
//判断质数
bool Isnum(int x) {
    if (x == 1)
        return false;
    for (int i = 2;i < x;i++)
        if (x % i == 0)
            return false;
    return true;
}
bool Ismir(int x) {
    int arr[10] = { 0 };
    int k = 0;
    while (x) {
        arr[k++] = x % 10;
        x /= 10;
    }
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            if (Isnum(arr[i] * 10 + arr[j]) && arr[i] != 0)
                return true;
        }
    }
    for (int i = k - 1; i >= 0; i--) {
        for (int j = i - 1; j >= 0; j--) {
            if (Isnum(arr[i] * 10 + arr[j]) && arr[i] != 0)
                return true;
        }
    }
    return false;
}
int main() {
    int a, b;
    while (cin >> a >> b) {
        int ret = 0;
        for (int i = a;i <= b;i++) {
            if (Ismir(i))
                ret++;
        }
        cout << ret << endl;
    }
    return 0;
}

//DNA序列
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, float>> vp(1010);
int main() {
    string s;
    int n;
    cin >> s >> n;
    int l = 0;
    int k = 0;
    while (l != s.size() - n + 1) {
        int cnt = 0;
        for (int i = l; i < l + n; ++i)
            if (s[i] == 'C' || s[i] == 'G')
                cnt++;
        vp[k++] = { l, (float)cnt / n };
        l++;
    }
    int keyi = 0;
    float Max = 0.0;
    for (int i = 0; i < k; ++i)
        if (vp[i].second > Max) {
            keyi = vp[i].first;
            Max = vp[i].second;
        }
    for (int i = keyi; i < keyi + n; ++i)
        cout << s[i];
    cout << endl;
    return 0;
}

//小乐乐改数字
#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) {
        if ((s[i] - '0') % 2 == 0)
            s[i] = '0';
        else
            s[i] = '1';
    }
    string ret;
    int i = 0;
    while (s[i] == '0')
        i++;
    for (; i < s.size(); ++i)
        ret += s[i];
    if (ret == "")
        cout << 0 << endl;
    else
        cout << ret << endl;
    return 0;
}
//十字爆破
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
int main() {
    long long  n, m;
    cin >> n >> m;
    long long  line[N];
    long long  col[N];
    vector<vector<long long >> v(n, vector<long long >(m));
    vector<vector<long long >> map(n, vector<long long >(m));
    for (long long i = 0; i < n; ++i)
        for (long long j = 0; j < m; ++j)
            cin >> map[i][j];
    for (long long i = 0; i < n; ++i) {
        long long  sum = 0;
        for (long long j = 0; j < m; ++j) {
            sum += map[i][j];
        }
        line[i] = sum;
    }
    for (long long i = 0; i < m; ++i) {
        long long  sum = 0;
        for (long long j = 0; j < n; ++j) {
            sum += map[j][i];
        }
        col[i] = sum;
    }
    for (long long i = 0; i < n; ++i) {
        for (long long j = 0; j < m; ++j) {
            v[i][j] = line[i] + col[j] - map[i][j];
        }
    }
    for (long long i = 0; i < n; ++i) {
        for (long long j = 0; j < m; ++j) {
            cout << v[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}
//比那名居的桃子
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long h[N];
long long s[N];
long long n, k;
long long x;
int main() {
    cin >> n >> k;
    cin >> h[0];
    for (long long i = 1; i < n; ++i) {
        cin >> x;
        h[i] = h[i - 1] + x;
    }
    cin >> s[0];
    for (long long i = 1; i < n; ++i) {
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    long long maxh = 0, mins = 0x3f3f3f3f;
    long long l = 0, r = 0;
    long long sum1 = 0;
    long long sum2 = 0;
    long long keyi;
    while (l < n - k + 1) {
        r = l + k - 1;
        if (l > 0) {
            sum1 = h[r] - h[l - 1];
            sum2 = s[r] - s[l - 1];
        }
        else {
            sum1 = h[r];
            sum2 = s[r];
        }

        if (sum1 > maxh) {
            maxh = sum1;
            mins = sum2;
            keyi = l;
        }
        else if (sum1 == maxh && sum2 < mins) {
            maxh = sum1;
            mins = sum2;
            keyi = l;
        }
        l++;
    }
    cout << keyi + 1 << endl;
    return 0;
}

// 压缩字符串
class Solution {
public:
    int Check(int x) {
        int cnt = 0;
        while (x) {
            x /= 10;
            cnt++;
        }
        return cnt;
    }
    string compressString(string param) {
        string ret;
        for (int i = 0; i < param.size(); ++i) {
            int tmp = param[i];
            int cnt = 0;
            while (param[i] == tmp) {
                cnt++;
                i++;
            }
            ret += tmp;
            if (cnt > 1) {
                int n = Check(cnt);
                if (n > 1) {
                    while (cnt) {
                        int i = pow(10, n - 1);
                        ret += cnt / i + '0';
                        cnt %= i;
                        n--;
                    }
                    if (n) {
                        ret += '0';
                        n--;
                    }
                }
                else if (n == 1) {
                    ret += cnt + '0';
                }
            }
            i--;
        }
        return ret;
    }
};
//chika和蜜柑
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<long long, long long> PII;// (酸，甜)
const int N = 2e5 + 10;
PII arr[N];
int main() {
    long long n, k;
    cin >> n >> k;
    for (long long i = 0; i < n; ++i)
        cin >> arr[i].first;
    for (long long i = 0; i < n; ++i)
        cin >> arr[i].second;
    sort(arr, arr + n, [&](const PII& a, const PII& b) {
        if (a.second != b.second)
        return a.second > b.second;
        else
            return a.first < b.first;
        });
    long long sums = 0;
    long long sumt = 0;
    for (long long i = 0; i < k; ++i) {
        sums += arr[i].first;
        sumt += arr[i].second;
    }
    cout << sums << ' ' << sumt << endl;
    return 0;
}
//0/1背包
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    const static int N = 1001;
    int v[N];
    int w[N];
    int dp[N][N] = { 0 };
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        for (int i = 0; i < vw.size(); i++) {
            v[i + 1] = vw[i][0];
            w[i + 1] = vw[i][1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - v[i] >= 0)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
        return dp[n][V];
    }
};

//699. 掉落的方块
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> ret(n);
        map<int, int> heightMap;
        heightMap[0] = 0; // 初始时从 0 开始的所有点的堆叠高度都是 0
        for (int i = 0; i < n; i++) {
            int size = positions[i][1];
            int left = positions[i][0], right = positions[i][0] + positions[i][1] - 1;
            auto lp = heightMap.upper_bound(left), rp = heightMap.upper_bound(right);
            int rHeight = prev(rp)->second; // 记录 right + 1 对应的堆叠高度（如果 right + 1 不在 heightMap 中）

            // 更新第 i 个掉落的方块的堆叠高度
            int height = 0;
            for (auto p = prev(lp); p != rp; p++) {
                height = max(height, p->second + size);
            }

            // 清除 heightMap 中位于 (left, right] 内的点
            heightMap.erase(lp, rp);

            heightMap[left] = height; // 更新 left 的变化
            if (rp == heightMap.end() || rp->first != right + 1) { // 如果 right + 1 不在 heightMap 中，更新 right + 1 的变化
                heightMap[right + 1] = rHeight;
            }
            ret[i] = i > 0 ? max(ret[i - 1], height) : height;
        }
        return ret;
    }
};

//小易的升级之路
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    ll n, x;
    cin >> n >> x;
    vector<ll>arr(n);
    for (ll i = 0; i < n; i++) {
        cin >> arr[i];
    }
    ll ret = x;
    for (ll i = 0; i < n; i++) {
        if (arr[i] > ret) {
            ret += gcd(arr[i], ret);
        }
        else {
            ret += arr[i];
        }
    }
    cout << ret << endl;
    return 0;
}
//礼物的最大价值
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int dp[201][201] = { 0 };
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};
//对称之美
#include <iostream>
#include <string>
#include <valarray>
#include <vector>
using namespace std;
vector<string>vs(101);
bool Check(string s, string t) {
    int hash[128] = { 0 };
    for (auto c : s)
        hash[c]++;
    for (auto c : t)
        if (hash[c] != 0)
            return true;
    return false;
}
// 双指针
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> vs[i];
    int flag = 1;
    int l = 0, r = n - 1;
    while (l < r) {
        if (!Check(vs[l], vs[r])) {
            flag = 0;
            break;
        }
        l++;
        r--;
    }
    if (flag == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

//大数加法
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        if (s.size() == 0)return t;
        if (t.size() == 0)return s;
        string ret;
        int n = s.size() - 1, m = t.size() - 1;
        int cnt = 0;//进位
        while (n >= 0 && m >= 0) {
            int tmp = s[n] - '0' + t[m] - '0' + cnt;
            ret += tmp % 10 + '0';
            cnt = tmp / 10;
            n--, m--;
        }
        while (n >= 0) {
            int tmp = s[n] - '0' + cnt;
            ret += tmp % 10 + '0';
            cnt = tmp / 10;
            n--;
        }
        while (m >= 0) {
            int tmp = t[m] - '0' + cnt;
            ret += tmp % 10 + '0';
            cnt = tmp / 10;
            m--;
        }
        if (cnt > 0) {
            ret += cnt + '0';
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};